package com.base.binarytree;

import java.util.Stack;

/**
 * @ClassName: HasPathSum
 * @Description: 112. 路径总和
 * 给你二叉树的根节点root 和一个表示目标和的整数targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum 。
 * <p>
 * 叶子节点 是指没有子节点的节点
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: li
 * @Date: 2021/8/18 11:30 上午
 */
public class HasPathSum {
    class Node {
        TreeNode node;
        int sum;

        public Node(TreeNode node, int sum) {
            this.node = node;
            this.sum = sum;
        }
    }

    public boolean hasPathSum(TreeNode root, int targetNum) {
        /**
         * 前序遍历迭代实现
         */
        if (root == null) {
            return false;
        }
        Stack<Node> stack = new Stack<>();
        stack.add(new Node(root, root.val));

        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            if (cur.node.left == null && cur.node.right == null && cur.sum == targetNum) {
                return true;
            }
            if (cur.node.right != null) {
                stack.add(new Node(cur.node.right, cur.sum + cur.node.right.val));
            }

            if (cur.node.left != null) {
                stack.add(new Node(cur.node.left, cur.sum + cur.node.left.val));
            }
        }
        return false;
    }

    public boolean hasPathSum1(TreeNode root, int targetNum) {
        /**
         * 递归实现
         */
        if (root == null) {
            return false;
        }
        if (root.left!=null&& root.right!=null){
            return targetNum == root.val;
        }
        return hasPathSum1(root.left,targetNum- root.val)||hasPathSum1(root.right, targetNum -root.val);
    }


}
